

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

The Zebra Puzzle

The following puzzle appeared in the magazine Life International on the 17th of December in the year 1962:

There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house.
The Norwegian lives in the first house.
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept.
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.

Furthermore, each of the five houses is painted in a different colour, their inhabitants are of different nationalities, own different pets, drink different beverages, and smoke different brands of cigarettes.

The objective of the zebra puzzle is to answers the following questions:

Who drinks water?
Who owns the zebra?

In the following, we formulate the zebra puzzle as a constraint satisfaction problem.

In order to succinctly express the constraints that all houses have different colours, the inhabitants have different nationalities etc., it is convenient to implement a function $\texttt{allDifferent}(V)$ that takes a set of variables $V$ and returns a set of formulas that is true if and only if all the variables from $V$ have different values.



In [ ]:

    
def allDifferent(Variables):
    'your code here'



In [ ]:

    
allDifferent({"English", "Spanish", "Japanese"})

The following global variables are convenient to code the puzzle.



In [ ]:

    
Nations   = { "English", "Spanish", "Ukrainian", "Norwegian", "Japanese" }
Drinks    = { "Coffee" , "Tea", "Milk", "OrangeJuice", "Water" }
Pets      = { "Dog", "Snails", "Horse", "Fox", "Zebra" }
Brands    = { "LuckyStrike", "Parliaments", "Kools", "Chesterfields", "OldGold" }
Colours   = { "Red", "Green", "Ivory", "Yellow", "Blue" }

The function $\texttt{zebraCSP}()$ returns a CSP that codes the zebra problem.



In [ ]:

    
def zebra_csp(): 
    Variables = Nations | Drinks | Pets | Brands | Colours
    Values    = { 1, 2, 3, 4, 5 }
    Constraints = { 'your code below'
                    # There are five houses.
                    # The Englishman lives in the red house.
                    # The Spaniard owns the dog.
                    # Coffee is drunk in the green house.
                    # The Ukrainian drinks tea.
                    # The green house is immediately to the right of the ivory house.
                    # The Old Gold smoker owns snails.
                    # Kools are smoked in the yellow house.
                    # Milk is drunk in the middle house.
                    # The Norwegian lives in the first house.
                    # The man who smokes Chesterfields lives in the house 
                    # next to the man with the fox.
                    # Kools are smoked in the house next to the house where 
                    # the horse is kept.
                    # The Lucky Strike smoker drinks orange juice.
                    # The Japanese smokes Parliaments.
                    # The Norwegian lives next to the blue house.
                  }
    # Furthermore, each of the five houses is painted in a different colour, 
    # their inhabitants are of different nationalities, 
    # own different pets, 
    # drink different beverages, and 
    # smoke different brands of cigarettes.
    return (Variables, Values, Constraints);



In [ ]:

    
from IPython.display import HTML

The function show_solution can be used to display the solution of the zebra puzzle as a table that is rendered as HTML.



In [ ]:

    
def show_solution(Solution):
    result  = '<table style="border:2px solid blue">\n'
    result += '<tr>'
    for name in ['House', 'Nationality',  'Drink', 'Animal', 'Brand', 'Colour']:
        result += '<th style="color:gold; background-color:blue">' + name + '</th>'
    result += '</tr>\n'
    for chair in range(1, 5+1):
        result += '<tr><td style="border:1px solid green">' + str(chair) + '</td>'
        for Class in [Nations, Drinks, Pets, Brands, Colours]:
            for x in Class:
                if Solution[x] == chair:
                    result += '<td  style="border:1px solid green">' + x + '</td>'
        result += '</tr>\n'
    result += '</table>'
    display(HTML(result))



In [ ]: